package ren.wxyz.algorithm.fifteenalgorithm;

import ren.wxyz.algorithm.demo.ComUtil;

/**
 * 合并排序，从小头开始比较两个数组的元素，将小的放入另一个数组中，将最后剩余也放入另一个数组
 * @author zxwang
 * @dateTime 2014年12月23日 下午7:17:49
 */
public class A01_MergeSequence {
	/**
	 * 禁止外部被初始化
	 */
	private A01_MergeSequence() {}

	/**
	 * 主方法
	 * @param args 命令行参数
	 */
	public static void main(String[] args) {
		int[] a = new int[] {2,4,6,8,10};
		int[] b = new int[] {1,3,5,7,9};
		int[] c = merge(a, b);
		ComUtil.printArray(c);
	}
	
	/**
	 * 合并排序
	 * @param a 第一个数组
	 * @param b 第二个数组
	 * @return 合并后的数组
	 */
	public static int[] merge(int[] a, int[] b) {
		int[] c = new int[a.length + b.length];
		
		int ai = 0;
		int bi = 0;
		int ci = 0;
		// 合并可比较的索引公共部分
		while (ai < a.length && bi < b.length) {
			if (a[ai] < b[bi]) {
				c[ci] = a[ai];
				ai++;
				ci++;
			}
			else {
				c[ci] = b[bi];
				bi++;
				ci++;
			}
		}
		
		// 将a剩余的加入c中
		while (ai < a.length) {
			c[ci] = a[ai];
			ai++;
			ci++;
		}
		// 将b剩余的加入c中
		while (bi < b.length) {
			c[ci] = b[bi];
			bi++;
			ci++;
		}
		
		return c;
	}

}
